#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""

priority = {
    '\\' : -100,    # 哨兵, 优先级最小

    '(' : -1,       # 除哨兵外: 符号中优先级最小的: 不会引起任何计算, 只作为')'匹配的边界
    ')' : -100,     # 优先级最低(越低越不可能和屁股后的字符相结合), 表明当前字符左边的符号优先级更高, 要先计算
                    # 遇到后, 括号内都要计算, until匹配到opes中的'('

    '+' : 1,
    '-' : 1,
    '*' : 2,        # 优先级越高越可能和屁股后字符相结合.
    '/' : 2,
    # '\\' : 3,
}


calc_map = {
    '\\' : lambda a,b : a ,     # TODO : check
    '+' : lambda a,b : a + b,
    '-' : lambda a,b : a - b,
    '*' : lambda a,b : a * b,
    '/' : lambda a,b : a / b,
    # '\\' : 3,
}


# return right <= left?
def prio_enable_calc(ope_left, ope_right):
    # if ope_left == '(':
    #     return False
    # if ope_right == '(':
    #     return False

    # '('特殊一些, 当'(' 比较时, 位于左边和右边的优先级不同.
    # (位于cmp函数右边时, 优先级很大, 也就是第一次进入时. 位于左边时, 优先级很小)
    # 说白了'('无论在哪不会引起计算, 只用来和')'配对.
    if ope_left == '(' or ope_right == '(':
        return False

    print('left, right', ope_left, ope_right)
    return priority[ope_right] <= priority[ope_left]

# const_nums = ["1", "2", "3", "4", "5", "6"]

def step_forward(nums, opes):
    # NOTE: WARNING: 注意不负责放入新符号: 无论是否step, 新符号都要在外面放入.
    # b = nums.pop() ; b = float(b)
    # a = nums.pop() ; a = float(a)
    b = nums.pop()
    a = nums.pop()
    o = opes.pop()
    new_num = calc_map[o](a, b)
    nums.append(new_num)
    return new_num

def try_more_steps(operator, nums, opes):
    if prio_enable_calc(opes[-1], operator):
        step_forward(nums, opes)
        return try_more_steps(operator, nums, opes)


def remains_forward(nums, opes):
    new_num = 0
    # process until: opes遇到'(', 或者len(opes) > 1
    while len(opes) > 1 and opes[-1] != '(':
        print('remians: nums, opes', nums, opes)
        new_num = step_forward(nums, opes)

    if opes[-1] == '(':
        opes.pop()

    # WARNING: NOTE 也可以不返回, 上层直接取nums[-1]即可
    return new_num

def process_emit_operator(operator, nums, opes):
    print('trigger ', operator, nums, opes)
    if operator == '(':
        # 不append, 上层调用方会append
        return

    if operator != ')':
        # trigger只负责触发'operator'之前的符号
        # 不等于命中概率高, 所以放在前面
        # 触发opes中所有比operator优先级高的操作: 4 - (2-3)*1 + 5/5, 遇到+号时, 先把(4 - -2)结账了, 再放入加号
        try_more_steps(operator, nums, opes)
    else:
        print('trigger )')
        remains_forward(nums, opes)

    return

def parse_int(expression, idx):
    end = ""

    while idx < len(expression):
        if expression[idx].isnumeric():
            end += (expression[idx])
            idx += 1
        else:
            break

    return end

def try_int(n):
    if n - int(n) <= 0.0000001:
        return int(n)
    return n

def calc(expression):
    nums = [0] # 目的为了没有输出数字时, 表达式值为0:例如输入 "",  "((()))"
    opes = ["\\"]
    # for ele in expression:
    # for i = 0; i < len(expression); i++ :
    idx = 0
    while idx < len(expression):
        ele = expression[idx]

        # 忽略空格
        if ele == " ":
            pass
            # continue

        elif ele == '(':
            opes.append(ele)
            # continue

        # 处理计算符号
        elif ele in priority:
            operator = ele
            process_emit_operator(operator, nums, opes)
            if operator != ')':
                # '(' 要放入, ')' 不放入
                opes.append(operator)        # 这里无论是否触发之前的计算, 新符号都要放入
            # continue

        # todo1 只支持个位数, 增加到10位数: 步步为营, 先处理最简单的问题.
        # todo2 只支持int, 要支持浮点数
        # 处理数字
        else:
            ele = parse_int(expression, idx)
            if ele == "":
                raise Exception("['%s'] is invalid character in expression " % expression[idx])

            nums.append(float(ele))
            if type(expression) == str:
                # 如果是list, 不用往前一步
                idx += len(ele) - 1

        idx += 1

        print('input, nums, opes ', ele, nums, opes)

    # while len(nums) > 1:
    #     # 5 * 3 + 5 * 3 + 5 * 3     # 字符串遍历完后, nums, opes中剩下多个数字和计算符号
    #     v = step_forward(nums, opes)
    # 5 * 3 + 5 * 3 + 5 * 3     # 字符串遍历完后, nums, opes中剩下多个数字和计算符号
    remains_forward(nums, opes)
    return try_int(nums[-1])


class Solution:
    """
    @param expression: a list of strings
    @return: an integer
    """
    def evaluateExpression(self, expression):
        # if not expression:
        #     return 0
        return calc(expression)


def main():
    print("start main")
    # v = calc(" 13/50*3+5*3+3*3-3-3* 3/33")
    # v = calc("5*(3+5)*3+(3/5 + 3 * 5) * (3 - 1) - ( 5 - 3 )")
    v = calc("(5*(3+5)*3+(3/5 + 3 * 5) * (3 - 1) - ( 5 - 3 ))")
    # v = calc("(5*(3+5)*3+((3/5 + 3 * 5)) * (3 - 1 * (3+5 * (3 + 5))) - ( 5 - 3 ))")
    # v = calc('4-(2-3)*2+5/5')
    # v = calc('2*6-(23+7)/(1+2)')
    print(v)

    s = Solution()
    input = ["(","(","(","(","(",")",")",")",")",")"]
    input = []
    # input = ["2", "*", "6", "-", "(","23", "+", "7", ")", "/", "(", "1", "+", "2", ")"]
    v = s.evaluateExpression(input)
    print(v)


if __name__ == "__main__":
    main()
